package com.qjc.demo.train.back;

/**
 * @ClassName: NQueues
 * @Description: 回溯算法：N皇后问题
 * 时间复杂度为：O(n!) 实际为O(n!/2)
 * 优缺点
 * 优点：
 * 回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解
 * 中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回
 * 溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。
 * 劣势：
 * 效率相对于低（动态规划）
 * @Author: qjc
 * @Date: 2022/5/4 11:52 AM
 */
public class NQueues {
    // 皇后数
    static int QUEUES = 8;
    // 下标表示QUEUE所在的行，值表示QUEUE所在的列
    int[] result = new int[QUEUES];

    // 判断该位置是否可以放置QUEUE
    private boolean isOK(int row, int col) {
        int leftUp = col - 1;
        int rightUp = col + 1;
        // 逐行往上考察每一行
        for (int i = row - 1; i >= 0; i--) {
            // 列上存在QUEUE
            if (result[i] == col) {
                return false;
            }
            // 左对角线存在queue
            if (leftUp >= 0) {
                if (result[i] == leftUp) return false;
            }
            // 右对角线存在queue
            if (rightUp < QUEUES) {
                if (result[i] == rightUp) return false;
            }
            leftUp--;
            rightUp++;
        }
        return true;
    }

    // 在每行放置queue
    public void setQueues(int row) {
        // 递归中断
        if (row == QUEUES) {
            printQueues();
            return;
        }
        // 在每行一次放置列，没有合适的则回到上一层
        for (int col = 0; col < QUEUES; col++) {
            if (isOK(row, col)) {
                // 设置列
                result[row] = col;
                // 开始下一行
                setQueues(row + 1);
            }
        }
    }

    // 打印
    private void printQueues() {
        for (int i = 0; i < QUEUES; i++) {
            for (int j = 0; j < QUEUES; j++) {
                if (result[i] == j) {
                    System.out.print("Q |");
                } else {
                    System.out.print("* |");
                }
            }
            System.out.println();
        }
        System.out.println("-----------------------------");
    }

    public static void main(String[] args) {
        NQueues nQueues = new NQueues();
        nQueues.setQueues(0);
    }

}
